package xyz.scootaloo.oj.offer

import org.junit.Test
import xyz.scootaloo.oj.ds.TreeNode
import xyz.scootaloo.oj.ds.helper.CollectionBuilder

/**
 * @author flutterdash@qq.com
 * @since 2021/4/11 17:56
 */
class P34 {

    private fun pathSum(root: TreeNode?, target: Int): List<List<Int>> {
        val res = ArrayList<List<Int>>()
        if (root == null)
            return res

        dfs(root, 0, target, ArrayDeque(), res)
        return res
    }

    private fun dfs(node: TreeNode, sum: Int, target: Int, path: ArrayDeque<Int>, res: ArrayList<List<Int>>) {
        path.addLast(node.`val`)
        if (node.left == null && node.right == null && (sum + node.`val`) == target) {
            res.add(ArrayList<Int>(path))
        }
        if (node.left != null) {
            dfs(node.left, sum + node.`val`, target, path, res)
        }
        if (node.right != null) {
            dfs(node.right, sum + node.`val`, target, path, res)
        }
        path.removeLast()
    }

    @Test
    fun test0() {
        val root = CollectionBuilder.initTree()
            .setRoot(5)
            .addLevel(4, 8)
            .addLevel(11, null, 13, 4)
            .addLevel(7, 2, null, null, null, null, 5, 1)
            .build()
        println(pathSum(root, 22))
    }

}
